/*
自己选择的路 ,跪着也要走完。朋友们 , 虽然这个世界日益浮躁起来,只
要能够为了当时纯粹的梦想和感动坚持努力下去 , 不管其它人怎么样,我
们也能够保持自己的本色走下去。
To the world , you will be a person , but to a person , you
will be the world .                               ——AKPower
*/
//作者:AKPower
//算法:
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;

ll f[1100], w[1100], v[1100], T, M, mem[110][1100];

// int main()
// {
//     IOS;
//     cin >> T >> M;
//     for (ll i = 1; i <= M; i++)
//     {
//         cin >> v[i] >> w[i];
//     }
//     ll maxn = 0;
//     for (ll i = 1; i <= M; i++)
//     {
//         for (ll j = T; j >= v[i]; j--)
//         {
//             f[j] = max(f[j - v[i]] + w[i], f[j]);
//             maxn = max(maxn, f[j]);
//         }
//     }
//     cout << maxn << endl;
//     // for(;;)
//     getchar();
//     getchar();
//     return 0;
// }

ll mem_dfs(ll pos, ll tleft)
{
    if (mem[pos][tleft])
        return mem[pos][tleft];
    if (pos == 0)
        return 0;
    ll df1 = -1, df2 = -1;
    df1 = mem_dfs(pos - 1, tleft); //不采
    if (tleft >= v[pos])
    {
        df2 = mem_dfs(pos - 1, tleft - v[pos]) + w[pos];
    }
    return mem[pos][tleft] = max(df1, df2);
}

int main()
{
    cin >> T >> M;
    for (ll i = 1; i <= M; i++)
    {
        cin >> v[i] >> w[i];
    }
    cout << mem_dfs(M, T) << endl;
    return 0;
}
